/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    const flag = new Array(board.length);
    const res = [];
    const tree = {};
    let wordSet = {}
    const buildTree = function(words){
        words.map(word=>{
            if(!wordSet[word[0]]) wordSet[word[0]] = {};
            wordSet[word[0]][word] = true;
            let t = tree;
            for(const w of word){
                if(!t[w]) t[w] = {};
                t = t[w];
            }
            t.word = word;
        })
    }
    buildTree(words);
    const dfs = function(x,y,tree){
        if(tree && tree.word && wordSet[tree.word[0]] && wordSet[tree.word[0]][tree.word]){
            res.push(tree.word);
            delete wordSet[tree.word[0]][tree.word];
            if(Object.keys(wordSet[tree.word[0]]).length == 0) delete wordSet[tree.word[0]];
        }
        if(x < 0 || y < 0 || x >= board.length || y >= board[0].length || !flag[x][y] || !tree){
            return;
        }
        flag[x][y] = false;
        const dx = [0,1,0,-1],dy = [1,0,-1,0];
        for(let i = 0; i < 4; i++){
            dfs(x+dx[i],y+dy[i],tree[board[x][y]]);
        }
        flag[x][y] = true;
    }
    for(let i = 0; i < board.length; i++){
        for(let j = 0; j < board[i].length; j++){
            const ch = board[i][j];
            if(wordSet[ch] && tree[ch]){
                for(let k = 0; k < flag.length; k++){
                    flag[k] = new Array(board[0].length).fill(true);
                }
                dfs(i,j,tree);
            }
        }
    }
    return res;
};